跳到主要内容

LCR 099.最小路径和

· 阅读需 7 分钟

1、题干​

给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。

说明：一个机器人每次只能向下或者向右移动一步。

 

示例 1：

输入：grid = [[1,3,1],[1,5,1],[4,2,1]]
输出：7
解释：因为路径 1→3→1→1→1 的总和最小。

示例 2：

输入：grid = [[1,2,3],[4,5,6]]
输出：12

 

提示：

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 200
  • 0 <= grid[i][j] <= 100

 

注意：本题与主站 64 题相同： https://leetcode-cn.com/problems/minimum-path-sum/

2、解法1-暴力DFS​

看完题目之后没多想误认为是走迷宫的题，于是写了一版暴力 DFS ，结果超时了。代码逻辑是从左上角到右下角进行深度遍历，并且累计路径和代入下一步计算。


超时的原因在于 ：通常走迷宫的题不会重复经过某个节点，因此时间复杂度是 O(mn)O(mn)，以 m,n<=200m,n <= 200 来算不会超时； 但这个题目的暴力 DFS 可以看做是遍历一棵高度为 n+m−1n+m-1 的二叉树，时间复杂度接近指数级的 2n+m−12^{n+m-1}，超时也不足为奇。


从网格左上角到右下角的最短路径长度为 n+m−1n+m-1，因此把它当成树的话高度为 n+m−1n+m-1


暴力DFS超时代码

var minPathSum = function (grid) {
    const m = grid.length, n = grid[0].length
    let min = Infinity;

    function dfs(i, j, sum) {
        if (i >= m || j >= n) return;
        sum += grid[i][j]

        if (i === m - 1 && j === n - 1) min = Math.min(min, sum);

        dfs(i + 1, j, sum);
        dfs(i, j + 1, sum);
    }

    dfs(0, 0, 0);
    return min;
};

3、暴力DFS-优化​

通常暴力 DFS 可以通过剪枝、记忆化等方式进行优化，这里采用了剪枝优化，优化后AC了但耗时 3208 ms 依然很高。


这里的问题在于：

  • 上述DFS代码属于暴力遍历所有情况并在终点时计算最小值，没有求局部最优解的倾向
  • 剪枝优化不稳定：这里剪枝的方式是记录节点前序路径和，当再次访问该节点时判断当前情况的前序路径和是否更小，以决定是否继续遍历以及是否更新该前序路径和，这种剪枝方式存在不稳定性，因为记录的前序路径和不是最小，后续遍历可能会有更小的前序路径和出现，所以这种剪枝没办法排除掉最小值以外的所有情况

4、代码​

var minPathSum = function (grid) {
    const m = grid.length, n = grid[0].length
    let min = Infinity, minPreSum = new Map();

    function dfs(i, j, sum) {
        const key = i + '-' + j;
        if (i >= m || j >= n || sum >= (minPreSum.get(key) || Infinity)) return;
        minPreSum.set(key, sum);

        sum += grid[i][j]

        if (i === m - 1 && j === n - 1) min = Math.min(min, sum);

        dfs(i + 1, j, sum);
        dfs(i, j + 1, sum);
    }

    dfs(0, 0, 0);
    return min;
};

5、执行结果​

  • 执行用时: 3208 ms
  • 内存消耗: 53 MB

6、解法2-记忆化DFS​

这个解法思路接近于动态规划， dfs 函数的意图是求局部最优解最终得到全局最优解，其中 dfs(i, j) 代表从终点 (m, n) 到点 (i, j) 的最小路径和，然后通过哈希表记录点 (i, j) 的最小路径和，后续再次遍历到该节点直接返回最小路径和，无需多余遍历与计算。


7、代码​

var minPathSum = function (grid) {
    const m = grid.length, n = grid[0].length
    const minSum = new Map();

    function dfs(i, j) {
        if (i >= m || j >= n) return Infinity;
        if (i === m - 1 && j === n - 1) return grid[i][j];

        const key = i + '-' + j;
        if (minSum.has(key)) return minSum.get(key);

        const min = Math.min(dfs(i + 1, j), dfs(i, j + 1)) + grid[i][j];
        return minSum.set(key, min), min;
    }

    return dfs(0, 0);
};

8、执行结果​

  • 执行用时: 76 ms
  • 内存消耗: 49.2 MB

9、解法3-动态规划​

解法2采用的是逆序累加和求解，这里为了方便理解采用顺序累加和进行求解。从题意可以看出对于任意节点 (i, j)，其最小路径和取决于上方节点 (i-1, j) 和左方节点 (i, j-1)，其值为左上两个节点中最小路径和的较小值加上自身的值。

  • dp 数组含义：dp 数组是一个 (m+1)*(n+1) 的数组，其中 dp[i][j] 表示从起点 (0, 0) 到点 (i, j) 的最小路径和，其中第一行和第一列只是为了方便计算，没有实际含义
  • 状态转移方程是：
    • i === 1 && j === 1 时：dp[i][j] = grid[i - 1][j - 1]
    • 其他情况：dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i - 1][j - 1]
  • dp[i][j] 对应的节点是 grid[i - 1][j - 1]，因此遍历 dp 数组时 i 和 j 都从下标 1 开始

10、代码​

var minPathSum = function (grid) {
    const m = grid.length, n = grid[0].length
    const dp = new Array(m + 1).fill(0).map(() => new Array(n + 1).fill(Infinity));

    for (let i = 1; i <= m; i++) {
        for (let j = 1; j <= n; j++) {
            if (i === 1 && j === 1) dp[i][j] = grid[i - 1][j - 1];
            else dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i - 1][j - 1];
        }
    }

    return dp[m][n];
};

11、执行结果​

  • 执行用时: 76 ms
  • 内存消耗: 44 MB

12、最后​

题解区有更优秀的动态规划解法，有降维 DP（一维）、有把原始数组 grid 作为 DP 数组等，主要降低了空间复杂度，很值得学习。